package dp;

import java.math.BigInteger;

public class P0801 {
    public int waysToStep(int n) {
        if (n <= 2) {
            return n;
        }
        BigInteger[] count = new BigInteger[n];
        count[0] = new BigInteger("1");
        count[1] = new BigInteger("2");
        count[2] = new BigInteger("4");
        for (int i = 3; i < n; i++) {
            count[i] = count[i - 1].add(count[i - 2]).add(count[i - 3]);
        }
        return count[n - 1].mod(new BigInteger("1000000007")).intValue();
    }

    public static void main(String[] args) {
        System.out.println(new P0801().waysToStep(61));
    }
}
